package example8;

//739.每日温度

import java.util.*;

public class LeetCode739 {
    public static void main(String[] args) {
        int[] temperatures1 = new int[]{73,74,75,71,69,72,76,73};
        int[] temperatures2 = new int[]{30,40,50,60};
        int[] temperatures3 = new int[]{30,60,90};
        int[] answer = new Solution739().dailyTemperatures(temperatures1);
        System.out.println(Arrays.toString(answer));
    }
}

class Solution739{
    //方法二：单调栈。
    /*
    * 维护一个栈，栈里面存储的是下标，保证这个栈从栈底到栈顶，下标对应的温度依次递减。
    * 遍历温度数组temperatures，遍历到第i个温度，看当前栈里面有没有元素，没有元素就直接入栈。
    * 如果有元素，就比较temperatures[i]和栈顶下标index对应的温度temperatures[index]，
    * 若temperatures[i] > temperatures[index]，则answer[index] = i - index，index出栈，
    * 继续比较下一个栈顶元素假设为index2，重复上面的操作直到栈为空或
    * temperatures[i] < temperatures[index2]，那么此时i就入栈，称为新的栈顶元素。
    * */
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        //注意：Stack类是线程安全的，内部加了synchronized锁，所以性能会显著降低。
        //而Deque没有加锁，所以单线程下Deque性能要高得多
//        Stack<Integer> stack = new Stack<>();
//        Deque<Integer> stack = new ArrayDeque<>();
        Deque<Integer> stack = new LinkedList<Integer>();
        for(int i=0;i<n;i++){
            while(!stack.isEmpty()){
                int index = stack.peek();
                if(temperatures[index] < temperatures[i]){
                    stack.pop();
                    answer[index] = i - index;
                }else{
                    break;
                }
            }
            stack.push(i);
        }
        return answer;
    }

    //方法一：暴力法。
    /*
    * 因为温度范围是30 - 100。所以可以定义一个数组arr，存储当前温度第一次出现的下标。
    * 然后反向遍历温度数组temperatures，然后对每个温度temperatures[i]，
    * 到arr中从temperatures[i]+1下标开始遍历到100，找到所有arr[j] > i的j，也就是
    * 找到所有温度比temperatures[i]高且在i后面的下标j，然后比较这里面的所有j，找到最小的一个j，
    * 就是当前i之后最近的一个更高温，将answer[i]赋值为最小的j - i;
    * */
    public int[] dailyTemperatures1(int[] temperatures) {
        int n = temperatures.length;
        int[] answer = new int[n];
        int[] arr = new int[101];
        arr[temperatures[n-1]] = n - 1;
        int min = n;
        for(int i=n-2;i>=0;i--){
            min = n;
            for(int j=temperatures[i]+1;j<101;j++){
                if(arr[j] > i){
                    min = Math.min(min,arr[j]);
                }
            }
            if(min != n)    answer[i] = min - i;
            arr[temperatures[i]] = i;
        }
        return answer;
    }
}
